import java.util.List;

public class SingleLinkedList {

    private ListNode head=null;//头节点引用本地初始化为空
    //将节点定义为内部类
    class ListNode{
        //数值域
        public int val;
        //引用域
        public ListNode next;

        //Node类的有参构造方法
        public ListNode(int val){
            this.val=val;
            this.next=null;
        }
    }

    //头插法
    public void addFirst(int data){
        ListNode listNode=new ListNode(data);
        listNode.next=head;
        head=listNode;
    }

    //尾插法
    public void addLast(int data){
        ListNode listNode=new ListNode(data);
        //判断头节点是否为空，为空则直接添加
        if(head==null){
            head=listNode;
        }
        //遍历链表找到最后一个节点
        ListNode current=head;
        while(current.next!=null){
            current=current.next;
        }
        current.next=listNode;

    }

    //底层方法，检查下标
    public void checkIndex(int index)throws AddIndexPosIlegalException{
        if(index<0||index>getSize()){
            throw new AddIndexPosIlegalException("下标非法");
        }
    }

    //底层方法，寻找某个下标直接前驱节点
    public ListNode findSuboneIndex(int index){
        ListNode current=head;
        int count=0;
        while(count!=index-1){
            current=current.next;
            count++;
        }
        return current;
    }


    //在指定下标插入数据
    public void addIndex(int index,int data){
        //解决下标非法异常
        try{
            checkIndex(index);
        }catch (AddIndexPosIlegalException e){
            e.printStackTrace();
        }
        //  判断是否为头插
        if(index==0){
            addFirst(data);
            return;
        }
        //判断是否为尾插
        if(index==getSize()){
            addLast(data);
            return;
        }
        //找到直接前驱节点
        ListNode subOneListNode=findSuboneIndex(index);
        //插入新节点
        ListNode listNode=new ListNode(data);
        listNode.next=subOneListNode.next;
        subOneListNode.next=listNode;

    }

    //删除第一次出现的值为key的节点
    public void remove(int key) {
        //判空
        if(head==null){
            return;
        }
        ListNode current = head;
        //后续以head.next判断的形式进行遍历无法涉及到开始节点
        //所以要对开始节点进行处理
        if (current.val == key) {
            head = null;
            return;
        }
        while (current.next != null) {
            if (current.next.val == key) {
                current.next = current.next.next;
                return;
            }
            current=current.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        //判空
        if(head==null){
            return;
        }
        //双引用遍历链表
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==key) {
                pre.next = cur.next;
            }else{
                pre=cur;
            }
            cur=cur.next;
        }
        //双引用遍历并没有涉及到头节点，所以最后对头节点进行处理
        if(head.val==key) {
            head = head.next;
        }
    }

    //查找链表中是否包含某值
    public boolean contains(int key){
         ListNode current=head;
         while(current!=null){
             if(current.val==key){
                 return true;
             }
         }
        return false;
    }

    //获取链表的长度
    public int getSize(){
        ListNode current=head;
        int count=0;
        //遍历全部链表
        while(current!=null){
            count++;
            current=current.next;
        }
        return count;
    }

    //展示整个链表
    public void display(){
        ListNode current=head;
        //遍历全部链表
        while(current!=null){
            System.out.print(current.val+" ");
            current=current.next;
        }
        System.out.println();
    }

    //清空整个链表
    public void clear(){
        //判空
        if(head==null){
            return;
        }
        //双引用遍历全部链表
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null){
            pre.next=null;
            pre=cur;
            cur=cur.next;
        }
        pre=null;
        head=null;
    }
}